public class sortedArrayToBST {
    /**
     * 将有序数组转换为二叉搜索树
     *
     * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
     * 平衡二叉搜索树。
     */
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){

        }
        TreeNode(int val){
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode method(int[] nums){
        return dfs(nums, 0, nums.length-1); //从中间元素开始进行查找
    }

    public TreeNode dfs(int[] nums, int lo, int hi){
        if(lo > hi){ //递归结束的条件
            return null;
        }
        // 递归查找到中间节点
        int mid= lo + (hi - lo)/2;
        TreeNode root = new TreeNode(nums[mid]);
        // 递归找不到root的左子树和右子树；
        root.left = dfs(nums,lo,mid-1);
        root.right = dfs(nums, mid+1, hi);
        return root;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        sortedArrayToBST solution = new sortedArrayToBST();
        TreeNode root = solution.method(nums);

        // 打印结果，可以通过中序遍历验证生成的二叉搜索树是否正确
        System.out.println("中序遍历结果：");
        inorderTraversal(root);
    }

    private static void inorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left);
        System.out.print(node.val + " ");
        inorderTraversal(node.right);
    }
}
